package leetcode_top;

import java.util.*;
import org.junit.*;

import utils.StringUtil;

public class Ex84 {
    class Solution {
        public int largestRectangleArea(int[] heights) {
            int len = heights.length, max = 0, h;
            Stack<Integer> stack = new Stack<>();
            // stack.push(item)
            int[] nums = new int[len + 2];
            System.arraycopy(heights, 0, nums, 1, len);
            heights = nums;
            for (int i = 0; i < len + 2; i++) {
                while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                    h = stack.pop();

                    /*
                     * 这句话到底什么意思？？？
                     * 
                     * 后面一个0好理解： 如果height[0]比较大，那么肯定可以把所有元素弹出；如果比较
                     */
                    max = Math.max(max, heights[h] * (i - stack.peek() - 1));
                }
                stack.push(i);
            }

            while (!stack.isEmpty()) {
                h = stack.pop();
                max = Math.max(max, heights[h] * (len + 2 - h));
            }
            return max;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums /*
                    * = new int[]{2,1,5,6,2,3}; nums = new int[]{2,4}
                    */;
        nums = new int[] { 2, 1, 2 };
        System.out.println(s.largestRectangleArea(nums));
    }

}
